// 1. 每次选择一个数字，好几种选择，再选下一个，又有好几种选择
// 2. 利用 hashSet 存储选过的数字，避免重复选择
// 3. 当选齐了，就生成了一个排列，用变量记录它是第几个，等于 k 就返回它
// 4. 不等于 k，就结束当前递归，回溯，撤销最后一个选择，进入别的分支继续搜索

var getPermutation = function (n, k) {
  let count = 0;
  let used = new Set();

  const helper = (temp) => {
    if (temp.length == n) {
      // 选齐了，生成了一个排列
      count++;
      if (count == k) {
        // 正好是第 k 个
        return temp.join(""); // 拼接成字符串，返回出来
      }
    }
    for (let i = 1; i <= n; i++) {
      if (used.has(i)) continue;
      temp.push(i);
      used.add(i);
      const res = helper(temp);
      temp.pop();
      used.delete(i);
      if (res) {
        // 有返回值，说明找到了，返回 res，结束
        return res;
      }
    }
    return; // 结束当前递归
  };
  return helper([]);
};
